DSC 40B

Problems tagged with "topological sorting"

Problem #267

Tags: topological sorting, lecture-13

Consider the graph \(G = (V, E)\) with \(V = \{a, b, c\}\) and \(E = \{(a, b)\}\).

How many valid topological sorts of this graph are there?

Solution

3

Problem #268

Tags: topological sorting, lecture-13

Consider the directed acyclic graph \(G = (V, E)\) with \(V = \{a, b, c, d\}\) and \(E = \{(a, b), (a,c), (a,d)\}\). How many topological sorts of this graph are there?

Solution

6

Problem #269

Tags: topological sorting, lecture-13

Let \(G = (V,E)\) be the directed graph with \(V = \{a, b, c, d, e\}\) and \(E = \{(a, b), (a, c), (a, d), (b, e), (c, e), (d, e)\}\). How many valid topological sorts of $V$ are there?

Solution

6

Problem #270

Tags: topological sorting, lecture-13

Find a topological sort of the graph shown below:

Solution

d a b c e

Problem #297

Tags: topological sorting, lecture-13

Suppose \(G\) is an acyclic directed graph. Let \(a\) and \(b\) be two nodes of \(G\) such that \(a\) appears before \(b\) in every possible topological sort of \(G\).

True or False: there must be a path from \(a\) to \(b\).

True False
Solution

True.

Suppose there were no path from \(a\) to \(b\). Then \(a\) is not among the nodes that have a path to \(b\). We could list \(b\) and all the nodes with a path to \(b\) first (in topological order), followed by the rest. This is a valid topological sort with \(b\) before \(a\).